Trigger Happy Jack

Prev Next

High Octane: Mixing Threads with Callbacks
or
You can't talk to a psycho like a normal human being
by Jonathan 'Wolf' Rentzsch (jon@redshed.net)

Prev Next

Last Year

Implementing Threaded IO on the Mac OS without bleeding from the ears.
Synchronous IO: Easy but locks up the machine until completed.
Asynchronous IO: Powerful but difficult.
Threaded IO: Easy and powerful but slow(er).
- Slowest: the develop model.
- Slow: the PowerPlant model.
- Slow: the polling model.
- Fast: XThreads.

Prev Next

Traditional Threading Methodology
(develop, PowerPlant and polling)

The thread enqueues some job and goes to sleep.
When the job is completed, the Toolbox fires the application-defined callback.
The callback marks the thread as awake and returns to the Toolbox.
Now, sometime later, the thread can pick up where it left off.

Prev Next

Traditional Threading Methodology Illustrated

Thread Callback
Enqueue the job
Go To Sleep
(Called from Toolbox)
Awake Thread
Return to Toolbox
Do Anything

Thread	Callback
Enqueue the job
Go To Sleep
	(Called from Toolbox)
	Awake Thread
	Return to Toolbox
Do Anything

Prev Next

Problems with the Traditional Threading Methodology

Going to sleep after enqueuing the job is a no-no. The job may complete and the callback fired after the job is enqueued, but before the thread is put to sleep.
This is known as "The Window of Death."
Solving The Window of Death:
- develop: two threads per job.
- PowerPlant: defer the callback until the thread is asleep.
- polling: don't sleep, just keep polling until job is done.

Prev Next

Problems with the Traditional Threading Methodology

All of the models have high, unpredictable latency. When the callback fires, it simply marks the thread as awake -- the callback itself doesn't do any work.
So now your thread is ready to be scheduled -- but it's in line behind every other thread in your application.
And that's including your main thread, which houses your event loop is may switch out your application.

Prev Next

XThreads: A Lower Latency Model

To fight this high latency, I tried to wrote my own thread scheduler that plugged into the Thread Manager's custom scheduler hook.
The custom scheduler hook is a joke!
- Sure, you can plug in your own scheduler, but you won't know what to schedule!

Prev Next

XThreads: A Lower Latency Model

My paper last year was largely about hacking the Thread Manager so you could actually accomplish what was advertised (a custom thread scheduler).
- Now your custom scheduler can access your thread queue.

Prev Next

XThreads: A Lower Latency Model

Once I had a custom scheduler that works as advertised, I could cut down on some of that latency.
I created a special "priority queue". When a callback fired, it would awaken the sleeping thread and place it into the priority queue.
My custom scheduler would always look in the priority queue first for threads to schedule.

Prev Next

XThreads: The Fastest Model Until Today

Especially with IO, callbacks are often called at interrupt or deferred task time.
XThreads still has an unpredictable latency since the threads are scheduled at system task time (i.e.: WaitNextEvent()). A single application can and will hog the processor.
It's for this reason alone that many programmers exclusively use callbacks (either that or they're masochists, which would explain the Apple connection).

Prev Next

Fight the Future (Latency)

Instead of mearly awakening a thread in a callback, the fastest way is to actually switch into the sleeping thread from the callback.

Thread	Callback
Mark thread as ineligible for time
Enqueue the job
Yield
	(Called from Toolbox)
	Push callback state onto special "pulsar" stack
	Switch to thread
Do Anything
Yield
	(Popped and reloaded from pulsar stack by the scheduler)
	Return to Toolbox

Prev Next

Red Shed Threads

The callback now jumps to the sleeping thread with the understanding it will be absolute first in line when the thread yields.
The callback "pulses" the thread -- stomp the gas, bash the brakes, return to the toolbox.
The callback may be called preemptively, but relies on cooperation to return to the Toolbox. Hence preemptive cooperation.
Red Shed Threads: an implementation of pulsars.

Prev Next

Red Shed Threads Pros

Fastest thread model around.
Writing protocols using threads is immeasurably easier than using callbacks, and 99% as fast.
How much does this context-switching cost you? I do it in <25 68K instructions, 30 PowerPC instructions.
That's completely reasonable, especially at deferred task time, where Open Transport lives.

Prev Next

Red Shed Threads Cons

Depending on where the thread is in its execution, it may be running at system task time, interrupt time or deferred task time.
This is unlike the formally clear separation between system task time application code and interrupt time callbacks.
However, it's trivial to write a function to block a thread until system task time, making it easier to write code that touches the Memory Manager.

Prev Next

Red Shed Threads & Toolbox:
Device & File Manager

The Device and File Manager use completion routines.
Each parameter block (and thus job) has an ioCompletion field.
Simply extend the parameter block to include the thread information and you can use one universal completion routine to pulse your threads.

Prev Next

Red Shed Threads & Toolbox:
Open Transport

You specify a notifier when opening an endpoint.
Use your context structure to keep track of which event your thread is waiting for. When ever your notifier is called, it can check the event to see if it should pulse your thread. Otherwise it's possible for your notifier to pulse your thread before your thread is ready.

Prev Next

Red Shed Threads & Toolbox:
Apple Events

Michael Gough and Steve Sisak came up with futures.
Futures transparently suspend a thread that attempts to access a reply to an Apple Event that hasn't come yet.
The Futures package allows threading of incoming Apple Events: by suspending the incoming event.

Prev Next

Red Shed Threads & Toolbox:
Apple Events

Suspending the event is undesirable from a speed and complexity standpoint.
Pulsars make it easy to create a new thread from inside the Apple Event handler and then jump right to the new thread.

Prev Next

Red Shed Threads & Mac OS X

Perhaps Mac OS X will have something similar to pulsars -- I doubt it.
Your Red Shed Thread-based application will definitely run under OS X's Blue Box.
The only semi-skanky thing Red Shed Threads does is move the stack pointer into the heap (thus it needs to disable the stack sniffer).
Under Mac OS X, there's a guard page between the stack and the heap. However, Red Shed Threads doesn't overwrite the page: it plops the stack pointer right into the heap.